1. Field of the Invention
The present invention relates to an error detection method which uses a convolutional code as an error correction code and a Viterbi decoding as its decoding in digital data transmission or the like.
2. Description of the Related Art
Viterbi decoding is a convolutional code method. Viterbi decoding will be explained in connection with a specific example of a convolutional code C with a constraint length K=3 and a coding rate R=1/2 generated by a convolutional encoder circuit 30 such as is shown in FIG. 1.
The convolutional encoder 30 comprises an input terminal 40, a first shift register F0 as a first delay operator, a second shift register F1 as a second delay operator, a first adder 42, a second adder 44, a first output terminal 46, and a second output terminal 48. Applied to the input terminal 40 is a train of information signals b.sub.i, b.sub.(i+1), . . . . The first shift register F0 receives the information signal train from the input terminal and outputs the information signal train delayed by a unit time. The second shift register F1 receives an output signal of the first shift register F0 and outputs the signal train further delayed by a unit time. Further, the first adder 42 adds together outputs of the input terminal 40, first shift register F0 and second shift register F1 and outputs its added result from the first output terminal 46 as a first output c.sub.i.sup.(1) =b.sub.(i-2) +b.sub.(i-1) +b.sub.i. The second adder 44 adds together the input signal from the input terminal 40 and the output of the second shift register F1 and outputs a second output c.sub.i.sup.(2) =b.sub.(i-2) +b.sub.i from the second output terminal 48.
The status S of the convolutional encoder 30 falls in one of the following four statuses depending on the states of the shift registers F0 and F1 shown in FIG. 1: EQU S0=(0,0), S1=(1,0), S2=(0,1) and S3=(1,1)
A trellis chart is a representation of transition statuses of a convolutional encoder circuit varying from the initial status S0 at every moment when an information signal is input. The trellis chart of the aforementioned code C is shown in FIG. 2. In this connection, it is assumed that the input information signal train has a length of J-K+1 followed by (K-1) of 0s for its information termination. In the trellis chart, in addition, a branch-like part is called merely a "branch" while a connection of more than one branch connected in series is called a "partial path".
In the trellis chart of FIG. 2, nodes in the first row are marked by S0, nodes in the second row are marked by S1, nodes in the third row are marked by S2, and nodes in the fourth row are marked by S3. The respective nodes or encoders have output states of (0,0), (0,1), (1,0) and (1,1). The branch shown by a dotted line has an input signal of 0, while the branch shown by a solid line has an input signal of 1. Further given to the branch parts are output statuses a, b, c and d of the encoders 30. In this connection, it is assumed that a=(0,0), b=(1,0), c=(0,1) and d=(1,1), left-side components are denoted by Ci.sup.(1), and right-side components are denoted by Ci.sup.(2).
A series of connected branches leading from the initial status S0 at t=t0 to the same status at t=tj are called a "path". This path is a path corresponding to a code word of the convolutional code C. The path will be referred to herein as a "code word path" where it is necessary to avoid its confusion with a partial path.
FIG. 3 shows partial paths in the trellis chart of the code C. Subsets of the code word corresponding to the partial paths are in the illustrated example: EQU CS.sub.1 =(00 00 11), and CS.sub.2 =(11 10 00)
In Viterbi decoding, each of paths CS.sub.1 and CS.sub.2 has a metric as an index determined on the basis of Hamming distance, Euclid distance or the like. The higher the certainty of the path, the larger is the metric of the path. Thus, when the metric of the path CS.sub.1 is larger than that of the path CS.sub.2 for example, the path CS.sub.2 discarded. At this time, all code word paths which include the path CS.sub.2 as a partial path are discarded from transmission code word candidates. Partial paths which remain without being discarded such as CS.sub.1 are known as surviving paths.
From the observation of the trellis chart of FIG. 2, it will be seen that there are present two partial paths which have the same branch state as shown in FIG. 3. Thus, it will be appreciated that there are always 2.sup.(k-1) of surviving paths at each time in a stationary state except for the both ends of the code word. And the number of surviving paths is decreased after a time t.sub.j-k+2 and at a time t.sub.j, the surviving path number becomes merely 1. And the single surviving path is decoded by trace-back into a transmission code.
FIG. 4 is a schematic block diagram of an error correction and error detection encoder which is based on a convolutional code and an error detection code. FIG. 5 shows an example of an encoder input sequence of information data to be converted into a convolutional code. FIG. 6 is a schematic block diagram of a prior-art error correction and error detection decoder which is based on Viterbi decoding and error detection decoding.
First of all, an error correction and detection encoder 31 of FIG. 4 comprises an error detection encoder circuit 32 and an error correction encoder circuit 33. More specifically, the error detection encoder circuit 32 receives input data and attaches to the input data such detection codes as cyclic redundancy check (CRC) codes (e.g., CRC1 denoted by reference numeral 34 and CRC2 denoted by numeral 35 in FIG. 5). In the example of FIG. 5, the input data is divided into three, data 1 to data 3 so that one CRC is attached to each of data 1 and data 3 in the form of divided inspection bits CRC1 and CRC2. The error correction encoder circuit 33 subjects an input signal received from the error detection encoder circuit 32 to a convolutional coding operation in an input order such as shown in FIG. 5.
Next, an error correction decoder 36 shown in FIG. 6 comprises an error correction decoder circuit 37 and an error detection decoder circuit 38. In more detail, the error correction decoder circuit 37 subjects received data to a Viterbi decoding operation. The error detection decoder circuit 38 receives a decoded result from the error correction decoder circuit 37, subjects it to a CRC error detecting operation, and outputs its error detection result together with decoded data. For example, the error detection decoder circuit 38 outputs an error detection flag 1 when detecting an error and an error detection flag 0 when failing to detect any error.
In the aforementioned error detection method, however, CRC encoding is carried out from both of data 1 and data 3 so that only the CRC error detection makes it impossible to perform error detection over the data 1 and data 3 independently, even when the data 1 has no error and the data 3 alone has an error or errors. For this reason, in the Viterbi decoding, in spite of the fact that an error in the decoded data occurs with a high probability in a burst manner (in the illustrated example, errors take place concentratedly in only one or two of the data 1 through data 3), since this error cannot be distinguished from the generation of errors in both the data 1 and data 3, it is disadvantageously impossible to realize efficient error detection. To avoid this, it is considered to attach a respectively independent CRC code to each of the data 1 and data 3. This method can attain independent error detection, but this also undesirably involves an increased number of redundant bits.
Kawabe et al. disclose an error detection system using convolutional code and Viterbi decoding to detect burst errors in JP-A-61-164352 (or JP-B-453337). Kawabe et al. propose to introduce detecting lengths of burst errors and durations of error-free regions and informing the lengths and the durations to the transmitter side of the system in order to select an adequate method for the transmission path and to repeat transmission. Kawabe et at. require an additional detecting device for lengths of burst errors and error-free durations.